package demo;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-06-21
 * Time: 9:39
 */
public class TestHeap {
    public int usedSize;
    public int[] elem;
    public TestHeap(){
        this.usedSize=0;
        this.elem = new int[11];
    }

    public  void swap(int[] nums,int i,int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    public void shiftDown(int[] nums,int parents,int len){
        int child = 2*parents+1;
        while(child<len){
            //找child中最大的那个
            while(child+1<len&&this.elem[child]<this.elem[child+1]){
                child++;
            }
            //此时child是最大的
            if(this.elem[parents]<this.elem[child]){
                swap(this.elem,parents,child);
            }else {
                break;
            }
            parents = child;
            child=2*parents+1;
        }

    }

    public void shiftUp(int child){
        int parents = (child-1)/2;
        while(parents>0){
            if(this.elem[parents]<this.elem[child]){
                swap(this.elem,parents,child);
                child = parents;
                parents = (child-1)/2;
            }else {
                break;
            }
        }
    }

    //检查是否增容
    public  void grow(){

    }

    //堆的插入
    public  void offer(int key){

            //将元素插入到数组的最后一个位置
        this.elem[this.usedSize] =key;
        //将这个数字开始向上调整
        shiftUp(usedSize);
        usedSize++;
    }

    //堆的删除
    public void poll(){

    }


    //复习堆排序
    public  void createHeap(int[] nums){
        //创建一个大根堆
        for(int p = (nums.length-1-1)/2;p>=0;--p){
            shiftDown(nums,p,nums.length);
        }
    }

}
